package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/30 10:54
 */
class P116 {

    class Node(var `val`: Int) {
        var left: Node? = null
        var right: Node? = null
        var next: Node? = null

        override fun toString(): String {
            return "Node(`val`=$`val`)"
        }
    }

    fun connect(root: Node?): Node? {
        if (root == null)
            return null

        val queue = ArrayDeque<Node>()
        queue.addLast(root)
        var level = 1

        while (queue.isNotEmpty()) {
            var nextLevel = 0
            for (i in 1..level) {
                val curNode = queue.removeFirst()

                if (i != level)
                    curNode.next = queue.first()
                curNode.left?.let { queue.addLast(it) }
                curNode.right?.let { queue.addLast(it) }
                nextLevel += 2
            }
            level = nextLevel
        }

        return root
    }

    @Test
    fun test0() {
        val node1 = Node(1)
        val node2 = Node(2)
        val node3 = Node(3)
        val node4 = Node(4)
        val node5 = Node(5)
        val node6 = Node(6)
        val node7 = Node(7)

        node1.left = node2
        node1.right = node3

        node2.left = node4
        node2.right = node5

        node3.left = node6
        node3.right = node7

        connect(node1)

        Console.log()
    }

}
